#define _CRT_SECURE_NO_WARNINGS 1

//一.面试题 17.04.消失的数字
//数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。
//你有办法在O(n)时间内完成吗？
//示例 1：
//输入：[3, 0, 1]
//输出：2
//示例 2：
//输入：[9, 6, 4, 2, 3, 5, 7, 0, 1]
//输出：8
//int missingNumber(int* nums, int numsSize) {
//	int x = 0;
//	for (int i = 0;i <= numsSize;i++)
//	{
//		x += i;
//	}
//	for (int i = 0;i < numsSize;i++)
//	{
//		x -= nums[i];
//	}
//	return x;
//}

//二. 189. 轮转数组
//给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//示例 1:
//输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
//输出 : [5, 6, 7, 1, 2, 3, 4] 解释 :
//	向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
//	向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
//	向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]
//1 <= nums.length <= 10^5
//- 2^31 <= nums[i] <= 2^31 - 1
//0 <= k <= 10^5

//法一：移首补尾法（超时） 时间O（N*K）      空间O（1）
//void rotate(int* nums, int numsSize, int k) {
//	for (int j = 0;j < k;j++)
//	{
//		int tmp = nums[numsSize - 1];
//		for (int i = numsSize - 1;i >= 1;i--)
//		{
//			nums[i] = nums[i - 1];
//		}
//		nums[0] = tmp;
//	}
//}

//法二：开辟新空间    时间O(N)   空间O(N)
//void rotate(int* nums, int numsSize, int k) {
//	k %= numsSize;
//	int arr[105] = { 0 };
//	int j = 0;
//	for (int i = (numsSize - k);i <= (numsSize - 1);i++, j++)
//	{
//		arr[j] = nums[i];
//	}
//	for (int i = 0;i <= (numsSize - k - 1);i++, j++)
//	{
//		arr[j] = nums[i];
//	}
//	for (int i = 0;i <= numsSize - 1;i++)
//	{
//		nums[i] = arr[i];
//	}
//}

//法三：三步旋转法   时间O(N)  空间O(1)
//void reverse(int* nums, int left, int right)
//{
//    while (left < right)
//    {
//        int tmp = nums[left];
//        nums[left] = nums[right];
//        nums[right] = tmp;
//        left++;
//        right--;
//    }
//}
//void rotate(int* nums, int numsSize, int k) {
//    k %= numsSize;
//    reverse(nums, numsSize - k, numsSize - 1);//1 旋转右部分
//    reverse(nums, 0, numsSize - k - 1);//2 旋转左部分
//    reverse(nums, 0, numsSize - 1);//3 整体旋转
//}

//三. 27. 移除元素
//给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，
// 并返回移除后数组的新长度。
//不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
//输入：nums = [3, 2, 2, 3], val = 3
//输出：2, nums = [2, 2]
//解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
//你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，
//而 nums = [2, 2, 3, 3] 或 nums = [2, 2, 0, 0]，也会被视作正确答案。

//int removeElement(int* nums, int numsSize, int val) {
//	//运用快慢指针思想
//	int slow = 0, fast = 0;
//	while (fast < numsSize)
//	{
//		if (nums[fast] != val)
//		{
//			nums[slow] = nums[fast];
//			fast++;
//			slow++;
//		}
//		else
//		{
//			fast++;
//		}
//	}
//	return slow;
//}

//四.26.删除有序数组中的重复项
//给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，
//返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
//由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说,
//如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
//将最终结果插入 nums 的前 k 个位置后返回 k 。
//不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
//输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
//输出：5, nums = [0, 1, 2, 3, 4]
//解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。
//不需要考虑数组中超出新长度后面的元素。

//int removeDuplicates(int* nums, int numsSize) {
//	//运用快慢指针思想    时间O(N)  空间O(1)
//	int slow = 0, fast = 1 ;
//	while (fast < numsSize)
//	{
//		if (nums[fast] != nums[slow])
//		{
//			nums[++slow] = nums[fast];
//			fast++;
//		}
//		else
//		{
//			fast++;
//		}
//	}
//	return slow + 1;//此时slow只是最后一个不同的下标
//}

//五.88.合并两个有序数组
//给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，
//分别表示 nums1 和 nums2 中的元素数目。
//请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
//注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，
//nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，
//后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
//示例 1：
//输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
//输出：[1, 2, 2, 3, 5, 6]
//解释：需要合并[1, 2, 3] 和[2, 5, 6] 。
//合并结果是[1, 2, 2, 3, 5, 6] ，其中斜体加粗标注的为 nums1 中的元素。
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//    //此题给的两个numsSize可以不用，用 m和n
//	//时间O(M+N)  空间O(1)
//	int end = n + m - 1;
//	while (n > 1 && m > 1)
//	{
//		if (nums2[m - 1] >= nums1[n - 1])//从后往前比较
//		{
//			nums1[end] = nums2[m - 1];
//			end--;
//			m--;
//		}
//		else
//		{
//			nums1[end] = nums1[n - 1];
//			end--;
//			n--;
//		}
//	}
//	while (n >= 0)//是nums[1]结束跳出的话，把nums[2]拷过去
//	{
//		nums1[end] = nums1[n - 1];
//	}
//}

//六.989.数组形式的整数加法
//整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。
//• 例如，对于 num = 1321 ，数组形式是[1, 3, 2, 1] 。
//给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
//
//示例 1：
//输入：num = [1, 2, 0, 0], k = 34
//输出：[1, 2, 3, 4]
//解释：1200 + 34 = 1234
//示例 2：
//输入：num = [2, 7, 4], k = 181
//输出：[4, 5, 5]
//解释：274 + 181 = 455
//• 1 <= num.length <= 10 ^ 4
//• 0 <= num[i] <= 9
//• num 不包含任何前导零，除了零本身
//• 1 <= k <= 10 ^ 4

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//#include<stdio.h>
//#include<stdlib.h>
//int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
//	int tmp = 0;
//	for (int i = 0;i < numSize;i++)
//	{
//		tmp = num[i] + tmp * 10;
//	}
//	int sum = tmp + k;
//	int count = 0;
//	tmp = sum;
//	while (tmp)
//	{
//		tmp /= 10;
//		count++;
//	}
//	*returnSize = count;
//	int* ptr = (int*)malloc(count * sizeof(int));
//	if (ptr == NULL)
//	{
//		exit(-1);
//	}
//	int* ret = ptr;
//	for (int i = count - 1;i >= 0;i--)
//	{
//		ptr[i] = (sum % 10);
//		sum / 10;
//	}
//	return ret;
//}
//int main()
//{
//	int arr[] = { 1,2,3,4 };
//	int x = 0;
//	addToArrayForm(arr, 4, 34, &x);
//	printf("%d", x);
//	return 0;
//}
//#include<stdio.h>
//#include<string.h>
//#include<stdlib.h>
//void reverse(int* p, int sz)
//{
//	int left = 0, right = sz - 1;
//	while (left < right)
//	{
//		int tmp = p[left];
//		p[left] = p[right];
//		p[right] = tmp;
//		left++;
//		right--;
//	}
//}
//int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
//	int count = 0;
//	int tmp = k;
//	while (tmp)
//	{
//		tmp /= 10;
//		count++;
//	}
//	int max = (count + 1) > (numSize + 1) ? (count + 1) : (numSize + 1);
//	int* ptr = (int*)calloc(max, sizeof(int));
//	int* p = ptr;
//	int* ret = ptr;
//	count = 0;
//	int j = 0, i = numSize - 1;
//	for (;i >= 0;i--, j++)
//	{
//		ptr[j] = num[i] + (k % 10) + ptr[j];
//		k /= 10;
//		if (ptr[j] >= 10)
//		{
//			ptr[j + 1] = ptr[j] / 10;
//			ptr[j] %= 10;
//		}
//		count++;
//	}
//	if (i == 0 && k != 0)
//	{
//		ptr[++j]= (k % 10) + ptr[j];
//	}
//	if(p[count]==0)
//	{
//		reverse(p, count);
//		*returnSize = count;
//	}
//	else
//	{
//		reverse(p, count+1);
//		*returnSize = count+1;
//	}
//	return ret;
//}
//int main()
//{
//	int arr[] = { 0 };
//	int x = 0;
//	addToArrayForm(arr, 1,23, &x);
//	printf("%d", x);
//	return 0;
//}
#include<stdio.h>
#include<stdlib.h>
int* singleNumbers(int* nums, int numsSize, int* returnSize) {

    int* arr = (int*)calloc(2, sizeof(int));
    int sum = 0;
    for (int i = 0; i < numsSize; i++)
    {
        sum ^= nums[i];
    }
    int count = 0;
    for (int i = 0; i < 32; i++)
    {
        if (sum & 1 << i) //循环判断第几位是1
        {
            count = i;//如果是1 记录下来
            break;
        }
    }
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] & 1 << count)
        {
            arr[0] ^= nums[i];
        }
        else
        {
            arr[1] ^= nums[i];
        }
    }
    *returnSize = 2;
    printf("[%d,%d]", arr[0], arr[1]);
    return arr;
}
int main()
{
    int nums[] = {1, 2, 10, 4, 1, 4, 3, 3};
    int sz = 0;
    singleNumbers(nums, 8, &sz);
    return 0;
}